package chapter2;

import java.util.Arrays;

public class QuickSort2 {
    public static void quickSort2(int[] arr,int l,int r){
        if (l>=r){
            return;
        }
        int leftBound = l-1;
        int rightBound = r;
        int pointer = l;//可以不用这一步赋值
        int num = arr[r];
        while (pointer < rightBound){
            if (arr[pointer] < num){
                swap(arr,++leftBound,pointer++);
            }else if(arr[pointer] == num){
                pointer++;
            }else{
                swap(arr,--rightBound,pointer);
            }
        }
        swap(arr,rightBound++,r);
        quickSort2(arr,l,leftBound);
        quickSort2(arr,rightBound,r);
    }
    public static void  swap(int[] arr,int x,int y){
        int tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }


    public static void main(String[] args) {
        int[] arr ={4,2,5,6,8,3,7,9,9,2,1};
        quickSort2(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}
